目錄：資料結構系列文章

佇列(Queue)是一種First-In-First-Out的資料結構
如同字面上意思，就像排隊買票的隊列一樣
先買完票的人才能先出去，進來後面排隊的人要等到前面的人都買完才能出去

使用c++實作

使用陣列(Array)實作

這裡是採用記憶體空間會重複使用的Circular Queue

#include <iostream>
using namespace std;

template <typename T>
class QueueArray
{
public:
    QueueArray() : front(-1), back(-1), capacity(1)
    {
        ptr = new T[capacity];
    }
    void Push(T data) // 把資料放到最後端
    {

        if ((back + 1) % capacity == front) // 如果每個位置都放滿了，把配置陣列大小變為2倍再放資料
        {
            DoubleCapacity();
        }
        if (isEmpty()) // 如果Queue為空，則Push時front要另外加1，讓front變為0
        {
            front++;
        }
        ptr[(back + 1) % capacity] = data;
        back = (back + 1) % capacity;
    }
    void Pop() // 把頂端的資料移除
    {
        if (isEmpty())
        {
            cout << "Queue is empty." << endl;
        }
        else
        {
            front++; // 只需要把front加1就行，因為之後如果有資料Push進來，會直接覆蓋掉原本的，不須花費成本再delete跟new
        }
    }
    bool isEmpty() // 回傳Queue是否為空
    {
        return (front == -1);
    }
    int getSize() // 回傳Queue大小
    {
        if (isEmpty())
        {
            return 0;
        }
        else if (front == back) // 如果front和back為同一個位置
        {
            return 1;
        }
        else if (front < back) // 如果front在back前面
        {
            return back - front + 1;
        }
        else // 如果front在back後面
        {
            return capacity - (front - back) + 1;
        }
    }
    T getFront() // 回傳最前端的資料
    {
        if (isEmpty())
        {
            cout << "Queue is empty." << endl;
            return 0; // 回傳0是因為不知道T是什麼型態，如果回傳別的數值會很容易出錯
        }
        return ptr[front];
    }
    T getBack() // 回傳最後端的資料
    {
        if (isEmpty())
        {
            cout << "Queue is empty." << endl;
            return 0; // 回傳0是因為不知道T是什麼型態，如果回傳別的數值會很容易出錯
        }
        return ptr[back];
    }

private:
    int front;            // 最前端的index
    int back;             // 最後端的index
    int capacity;         // 目前配置空間的大小
    int *ptr;             // 目前配置的陣列(第一個元素的指標)
    void DoubleCapacity() // 把配置的陣列變成兩倍的大小
    {
        int *newptr = new int[capacity * 2];
        int j = front - 1;
        for (int i = 0; i < capacity; i++) // 把舊的陣列裡的資料複製到新的陣列
        {
            newptr[i] = ptr[(++j) % capacity];
        }
        delete[] ptr;
        ptr = newptr;
        front = 0;
        back = capacity - 1;
        capacity *= 2;
    }
};

int main()
{
    QueueArray<int> q;
    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(24);
    cout << "After push 24:\n";
    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(8);
    q.Push(23);
    cout << "After push 8, 23:\n";
    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Pop();
    cout << "After pop 24:\n";
    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(13);
    cout << "After push 13:\n";
    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Pop();
    cout << "After pop 8:\n";
    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(35);
    cout << "After push 35:\n";
    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(9);
    cout << "After push 9:\n";
    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(64);
    cout << "After push 64:\n";
    cout << q.isEmpty() << " " << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    return 0;
}

output:

Queue is empty.
Queue is empty.
1 0 0 0
0 24 24 1
0 24 23 3
0 8 23 2
0 8 13 3
0 23 13 2
0 23 35 3
0 23 9 4
0 23 64 5

使用鏈結串列(Linked List)實作

一樣我們稍微修改一下之前的linklist後就直接繼承
SinglyLinkedList.h

#include <iostream>
using namespace std;

template <typename T>
class SinglyLinkedList; // 為了將class SinglyLinkedList設成class ListNode的friend，必須先宣告

template <typename T>
class ListNode
{
public:
    ListNode(T x) : value(x), next(0) {} // 使用c++的成員初始化串列，將value初始化為x，next初始化為0
private:
    T value;
    ListNode<T> *next;
    friend class SinglyLinkedList<T>; // 將class SinglyLinkedList宣告為friend，讓class SinglyLinkedList可以存取ListNode的private成員
};

template <typename T>
class SinglyLinkedList
{
public:
    SinglyLinkedList() : head(0), size(0),tail(0) {}
    int getSize() // 回傳list資料個數
    {
        return size;
    }
    bool isEmpty() // 回傳list是否為空
    {
        return head == 0;
    }
protected: // 設為protected是因為不想讓非成員函式可以存取到
    void PushFront(T data) // 在list的最前端塞入資料
    {
        ListNode<T> *NewNode = new ListNode<T>(data);
        if (head == 0)
        {
            head = NewNode;
            tail = NewNode;
        }
        else
        {
            NewNode->next = head;
            head = NewNode;
        }
        ++size;
    }
    void PushBack(T data) // 在list的最後端塞入資料
    {
        if (head == 0)
        {
            PushFront(data);
        }
        else
        {
            ListNode<T> *NewNode = new ListNode<T>(data);
            tail->next=NewNode;
            tail = NewNode;
            ++size;
        }
    }
    ~SinglyLinkedList()
    {
        ListNode<T> *current = head;
        while (current != 0)
        {
            ListNode<T> *NextNode = current->next;
            delete current;
            current = NextNode;
        }
        head = 0; // 當指標被delete後, 將其指向NULL, 可以避免不必要bug
    }
    void PopFront() // 移除list中最前端的資料
    {
        if (head == 0)
        {
            cout << "List is empty." << endl;
        }
        else if(head!=0&& head->next==0) // 當list只有一筆資料時
        {
            delete head;
            head = 0;
            tail = 0;
            --size;
        }
        else
        {
            ListNode<T> *NextNode = head->next;
            delete head;
            head = NextNode;
            --size;
        }
    }
    T getHead() // 回傳第一個資料
    {
        if (isEmpty())
        {
            cout << "List is empty." << endl;
            return 0;
        }
        else
        {
            return head->value;
        }
    }
    T getTail() // 回傳最後一個資料
    {
        if (isEmpty())
        {
            cout << "List is empty." << endl;
            return 0;
        }
        else
        {
            return tail->value;
        }
    }
private:
    ListNode<T> *head;
    ListNode<T> *tail;
    int size;
};

#include <iostream>
#include "SinglyLinkedList.h"
using namespace std;

template <typename T>
class QueueList : public SinglyLinkedList<T>
{
public:
    void Push(T data) // 在最後端放入資料
    {
        SinglyLinkedList<T>::PushBack(data);
    }
    void Pop() // 移除最前端的資料
    {
        if (SinglyLinkedList<T>::isEmpty())
        {
            cout << "Queue is empty." << endl;
        }
        else
        {
            SinglyLinkedList<T>::PopFront();
        }
    }
    T getFront() // 取得最前端的資料
    {
        if (SinglyLinkedList<T>::isEmpty())
        {
            cout << "Queue is empty." << endl;
            return 0;
        }
        else
        {
            SinglyLinkedList<T>::getHead();
        }
    }
    T getBack() // 取得最後端的資料
    {
        if (SinglyLinkedList<T>::isEmpty())
        {
            cout << "Queue is empty." << endl;
            return 0;
        }
        else
        {
            SinglyLinkedList<T>::getTail();
        }
    }
};

int main()
{
    QueueList<int> q;
    cout << q.isEmpty() << endl;
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(24);
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Pop();
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(8);
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Pop();
    cout << q.isEmpty() << endl;
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(23);
    cout << q.isEmpty() << endl;
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(13);
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Pop();
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(35);
    q.Push(36);
    cout << q.isEmpty() << endl;
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Pop();
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Push(38);
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Pop();
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    q.Pop();
    cout << q.getFront() << " " << q.getBack() << " " << q.getSize() << endl;
    cout << q.isEmpty() << endl;
    return 0;
}

output:

1
Queue is empty.
Queue is empty.
0 0 0
24 24 1
Queue is empty.
Queue is empty.
0 0 0
8 8 1
1
Queue is empty.
Queue is empty.
0 0 0
0
23 23 1
23 13 2
13 13 1
0
13 36 3
35 36 2
35 38 3
36 38 2
38 38 1
0

使用python實作

class Queue:
    def __init__(self):
        self.queue = []  # 使用串列來實作
        self.size = 0

    def Push(self, data):  # 把資料放到最後端
        self.queue.append(data)  # append函式 把資料加進串列的末端
        self.size += 1

    def Pop(self):  # 把最前端的資料移除
        if self.size == 0:
            print("Queue is empty.")
        else:
            self.queue = self.queue[1:]  # 把串列的第一個元素移除
            self.size -= 1

    def getFront(self):
        if self.size == 0:
            print("Queue is empty.")
            return 0
        else:
            return self.queue[0]

    def getBack(self):  # 回傳最後端的資料
        if self.size == 0:
            print("Queue is empty.")
            return 0
        else:
            return self.queue[self.size - 1]

    def isEmpty(self):  # 回傳queue是否為空
        return self.size == 0

    def getSize(self):  # 回傳queue大小
        return self.size


def main():
    s = Queue()
    s.Pop()
    print(s.isEmpty())
    print(s.getFront())
    print(s.getBack())
    print(s.getSize())
    s.Push(2)
    print(s.isEmpty())
    print(s.getFront(), end=" ")
    print(s.getBack(), end=" ")
    print(s.getSize())
    s.Push(4)
    print(s.getFront(), end=" ")
    print(s.getBack(), end=" ")
    print(s.getSize())
    s.Push(6)
    print(s.getFront(), end=" ")
    print(s.getBack(), end=" ")
    print(s.getSize())
    s.Pop()
    print(s.isEmpty())
    print(s.getFront(), end=" ")
    print(s.getBack(), end=" ")
    print(s.getSize())
    s.Pop()
    print(s.getFront(), end=" ")
    print(s.getBack(), end=" ")
    print(s.getSize())
    s.Push(8)
    print(s.getFront(), end=" ")
    print(s.getBack(), end=" ")
    print(s.getSize())
    s.Push(10)
    print(s.isEmpty())
    print(s.getFront(), end=" ")
    print(s.getBack(), end=" ")
    print(s.getSize())
    s.Pop()
    print(s.getFront(), end=" ")
    print(s.getBack(), end=" ")
    print(s.getSize(), end=" ")
    print(s.isEmpty())


if __name__ == "__main__":
    main()

output:

Queue is empty.
True
Queue is empty.
0
Queue is empty.
0
0
False
2 2 1
2 4 2
2 6 3
False
4 6 2
6 6 1
6 8 2
False
6 10 3
8 10 2 False

上一篇：資料結構 堆疊(Stack)